package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/12 10:33
 */
public class NumberOfCombinations {


    public static void main(String[] args) {
        NumberOfCombinations test = new NumberOfCombinations();

        // 101
//        String num = "9999999999999";

        // 231
//        String num = "9999999999999999";

        // 22
//        String num = "99999999";

        // 3
//        String num = "999";

        // 22
//        String num = "9999999999";

        // 0
//        String num = "094";

        // 2
//        String num = "327";

        // 2
        String num = Utils.getStr(3500, '0', '0');

        int i = test.numberOfCombinations(num);
        System.out.println(i);
    }

    public int numberOfCombinations(String num) {
        char[] chars = num.toCharArray();
        if (chars[0] == '0') {
            return 0;
        }
        int length = num.length();
        long[][] values = new long[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = i; j > 0; j--) {
                if (chars[j] == '0') {
                    values[j][i] = (values[j][i] + (j + 1 <= i ? values[j + 1][i] : 0)) % 1000000007;
                    continue;
                }
                int end = (j << 1) - i - 1;
                if (end < 0) {
                    values[j][i] = values[0][j - 1];
                } else {
                    int size = i - j + 1;
                    boolean flag = true;
                    int k = 0;
                    while (k < size) {
                        if (chars[k + end] != chars[k + j]) {
                            flag = chars[k + end] < chars[k + j];
                            break;
                        }
                        k++;
                    }
                    if (flag) {
                        values[j][i] = values[end][j - 1];
                    } else {
                        if (end + 1 <= j - 1) {
                            values[j][i] = values[end + 1][j - 1];
                        }
                    }
                }
                values[j][i] = (values[j][i] + (j + 1 <= i ? values[j + 1][i] : 0)) % 1000000007;
            }
            values[0][i] = (1 + (1 <= i ? values[1][i] : 0)) % 1000000007;
        }
        return (int) (values[0][length - 1] % 1000000007);
    }

}
